package org.hhchat.leetcode.dp;

/**
 * Created by HMH on 2017/4/5.
 fantastic 思路：

 https://discuss.leetcode.com/topic/76830/java-9-lines-dp-solution-easy-to-understand-with-improvement-to-o-n-space-complexity

 双人动态规划，拆分的子问题要拆分为一个统一适用的递推公式
 */
public class code486 {
    public static class Solution {
        public boolean PredictTheWinner(int[] nums) {
            if (nums == null) { return true; }
            int len = nums.length;
            int dp[][] = new int[len][len];
            if ((len & 1) == 0) { return true; }
            for(int i=0;i<len;i++) {
                dp[i][i] = nums[i];
            }
            //这里需要注意的是，需要使用len从0-n-1作为一层循环，保证计算i-j的时候，i-(j-1)和(i+1)-j都已经计算过。
            //dp 增长区域长度，保证小区间先计算完成（非递归写法）
            for(int l=1;l<len;l++) {
                for(int i=0;i<len-l;i++) {
                    int j = i + l;
                    dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
                }
            }
            return dp[0][len - 1] >= 0;
        }
    }
    public static void main(String[] args){
        System.out.println(new Solution().PredictTheWinner(new int[]{1, 5, 2}));
    }
}
